/*
 * @Author: gitee_com_zb
 * @Date: 2024-11-15 11:11:41
 * @LastEditors: gitee_com_zb
 * @LastEditTime: 2024-11-15 11:11:47
 * @FilePath: /lzb/GiteeCode/algorithm/优选算法43.颜色分类(medium).cpp
 * @Description: 题目链接 https://leetcode.cn/problems/sort-colors
 */
class Solution {
public:
    void sortColors(vector<int>& nums) {
        // 分治--快排
        // 用3个指针将数组分为四个区间,[0,left][left+1,i-1][i,right-1][right,n-1]
        // i不断向后遍历,判断当前值将值添加到对应区间即可
        int n = nums.size();
        int left = -1, right = n;
        for(int i = 0; i < right;) {
            if(nums[i] == 0) swap(nums[++left],nums[i++]);
            else if(nums[i] == 1) i++;
            else swap(nums[--right],nums[i]);
        }
    }
};